1328E - Tree Queries - CodeForces Solution

from collections import defaultdict, deque, Counter
import sys
from decimal import *
from heapq import heapify, heappop, heappush
import math
import random
import string
from copy import deepcopy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce, lru_cache
from bisect import bisect_left, bisect_right

def input():
    return sys.stdin.readline().rstrip()
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getListGraph():
    return list(map(lambda x:int(x) - 1, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]

mod = 10 ** 9 + 7
MOD = 998244353

inf = float('inf')
eps = 10 ** (-12)
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]


class Doubling():
    def __init__(self, n, edges, root):
        self.n = n
        self.logk = n.bit_length()
        self.doubling = [[-1] * self.n for _ in range(self.logk)]
        self.depth = [-1] * N
        self.depth[root] = 0
                par = [-1] * N
        pos = deque([root])
        while len(pos) > 0:
            u = pos.popleft()
            for v in edges[u]:
                if self.depth[v] == -1:
                    self.depth[v] = self.depth[u] + 1
                    par[v] = u
                    pos.append(v)
                for i in range(self.n):
            self.doubling[0][i] = par[i]
        for i in range(1, self.logk):
            for j in range(self.n):
                if self.doubling[i - 1][j] == -1:
                    self.doubling[i][j] = -1
                else:
                    self.doubling[i][j] = self.doubling[i - 1][self.doubling[i - 1][j]]

    def upstream(self, s, t):
        if t == 0:
            return s
        now = s
        for k in range(self.logk):
            if t & (1 << k):
                now = self.doubling[k][now]
        return now

N, M = getNM()
E = [[] for i in range(N)]
for _ in range(N - 1):
    a, b = getNM()
    E[a - 1].append(b - 1)
    E[b - 1].append(a - 1)

D = Doubling(N, E, 0)
for _ in range(M):
    q = getListGraph()
    q = [[D.depth[D.doubling[0][i]], D.doubling[0][i]] for i in q[1:] if i != 0]
    q.sort()
    ans = 'YES'
    for i in range(len(q) - 1, 0, -1):
        d1, p1 = q[i - 1]
        d2, p2 = q[i]
        if D.upstream(p2, d2 - d1) != p1:
            ans = 'NO'
    print(ans)